package algorithms.question.class14;

import common.util.MyUtil;

/**
 * https://leetcode-cn.com/problems/first-missing-positive
 *
 * @author guichang
 * @date 2021/8/11
 */

@SuppressWarnings("all")
public class Code6_缺失的第一个正数 {
    // 有效区和垃圾区

    public static void main(String[] args) {
        int[] arr = MyUtil.createRandomArray(10, -3, 20);
        MyUtil.print(firstMissingPositive(arr));
    }

    public static int firstMissingPositive(int[] arr) {
        if (arr == null || arr.length == 0) {
            return 1;
        }
        int L = 0; // <L的都是有效区
        int R = arr.length; // >R的都是垃圾区
        while (L < R) { // L==R就结束了
            // L上的位置有效
            if (arr[L] == L + 1) {
                L++;
                continue;
            }
            // L上的位置无效，R向左移动一位并与L交换
            if (arr[L] <= L || arr[L] > R || arr[arr[L] - 1] == arr[L]) {
                swap(arr, L, --R);
                continue;
            }
            // L与(arr[L]-1)交换
            swap(arr, L, arr[L] - 1);
        }
        return L + 1;
    }

    private static void swap(int[] arr, int i, int j) {
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }

}